733 Flood Fill

• 給一張圖像矩陣，從一個起點開始把所有相鄰（上下左右）的同色區域改成新的顏色。
• kotlin, DFS

class Solution {
    fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, newColor: Int): Array<IntArray> {
        val startColor = image[sr][sc]
        if (startColor == newColor) return image

        fun dfs(r: Int, c: Int) {
            if (r !in image.indices || c !in image[0].indices) return
            if (image[r][c] != startColor) return
            image[r][c] = newColor
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        }

        dfs(sr, sc)
        return image
    }
}

• follow up
  • 如何用 BFS 實現？（用 queue 替代遞迴）
  • 如果要處理 8 向連接（含對角線），怎麼改？（多加 4 個方向）
  • 如果矩陣非常大（例如 10000x10000），如何避免 StackOverflow？（改用 BFS iterative）
  • 延伸題：LeetCode 200 (Number of Islands)，與 Flood Fill 本質相同。